package huadi.algorithm.sort;

/**
 * ShellSort 希尔排序
 * 
 * @author Huadi
 */
public class ShellSort { // uncompleted
	public static void sort(int[] array) {
		int stepSize = array.length / 3;
		while (stepSize > 0) {
			insertionSortWithStep(array, stepSize);
			stepSize--;
		}
	}

	private static void insertionSortWithStep(int[] array, int stepSize) {
		for (int i = 0; i < array.length - 1; i += stepSize) { // fix it
			int j = i;

			// >> Insertion sort
			int key = array[j];
			while (j >= 0 && array[j - stepSize] > key) {
				array[j] = array[j - stepSize];
				j -= stepSize;
			}
			array[j] = key;
			// << Insertion sort

		}
	}

}
